package twoD;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * @author pengfei.hpf
 * @date 2020/3/29
 * @verdion 1.0.0
 * 1162. 地图分析
 * 你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
 *
 * 我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
 *
 * 如果我们的地图上只有陆地或者海洋，请返回 -1。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：[[1,0,1],[0,0,0],[1,0,1]]
 * 输出：2
 * 解释：
 * 海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
 * 示例 2：
 *
 *
 *
 * 输入：[[1,0,0],[0,0,0],[0,0,0]]
 * 输出：4
 * 解释：
 * 海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。
 *
 *
 * 提示：
 *
 * 1 <= grid.length == grid[0].length <= 100
 * grid[i][j] 不是 0 就是 1
 */
public class MaxDistance {

    public int maxDistance(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return -1;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dir = new int[][]{{-1, 0}, {0, -1}, {0,1}, {1, 0}};
        int[][] dis = new int[m][n];
        for(int[] d: dis){
            Arrays.fill(d, Integer.MAX_VALUE);
        }
        Queue<int[]> queue = new ArrayDeque<>();
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                if(grid[i][j] == 1){
                    dis[i][j] = 0;
                    for(int a = 0; a < dir.length; a ++){
                        int r = i + dir[a][0];
                        int c = j + dir[a][1];
                        if(r >= 0 && c >=0 && r < m && c < n){
                            if(grid[r][c] == 0){
                                grid[r][c] = -1;
                                dis[r][c] = 1;
                                queue.add(new int[]{r, c});
                            }
                        }
                    }
                }
            }
        }
        if(queue.isEmpty()){
            return -1;
        }
        int max = 0;
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int i = cur[0];
            int j = cur[1];
            for(int a = 0; a < dir.length; a ++){
                int r = i + dir[a][0];
                int c = j + dir[a][1];
                if(r >= 0 && c >=0 && r < m && c < n){
                    if(dis[i][j] + 1 < dis[r][c]){
                        dis[r][c] = dis[i][j] + 1;
                        queue.add(new int[]{r, c});
                        if(dis[r][c] > max){
                            max = dis[r][c];
                        }
                    }
                }
            }
        }
        return max;
    }

    public static void main(String[] args){
        System.out.println(new MaxDistance().maxDistance(new int[][]{{1,0,0},{0,0,0},{0,0,0}}));
    }
}
